package midalgorithms.sortandsearch;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class _06MergeArea {
    public static int[][] merge(int[][] intervals) {
        if (intervals.length <= 1){
            return intervals;
        }
        List<int[]> list = new LinkedList<>();
        for (int i = 0;i < intervals.length - 1;i++){
            int minIndex = i;
            for (int j = i;j < intervals.length;j++){
                if (intervals[j][0] < intervals[minIndex][0]){
                    minIndex = j;
                }
            }
            //  交换intervals[i] 和 intervals[minIndex]
            if (i != minIndex){
                swapArr(intervals,i,minIndex);
            }
        }
        //  两个数组a[],b[]可以合并的充要条件是：(a[0]<=b[0] && a[1]>=b[0]) || (a[0]>=b[0] && a[0]<=b[1])
        //  类似贪心算法，但是贪心算法要求数组是已经排序后的数组
        for (int i = 0;i < intervals.length - 1;i++){
            if (canMerge(intervals[i],intervals[i+1])){
                intervals[i+1][0] = Math.min(intervals[i][0],intervals[i+1][0]);
                intervals[i+1][1] = Math.max(intervals[i][1],intervals[i+1][1]);
            }else {
                list.add(intervals[i]);
            }
        }
        list.add(intervals[intervals.length-1]);
        int[][] res = new int[list.size()][2];
        for (int i = 0;i < list.size();i++){
            res[i] = Arrays.copyOf(list.get(i),2);
        }
        return res;
    }

    private static void swapArr(int[][] intervals, int i, int minIndex) {
        int temp = intervals[i][0];
        intervals[i][0] = intervals[minIndex][0];
        intervals[minIndex][0] = temp;

        temp = intervals[i][1];
        intervals[i][1] = intervals[minIndex][1];
        intervals[minIndex][1] = temp;
    }

    private static boolean canMerge(int[] a, int[] b) {
        if (a[0] > b[1] || b[0] > a[1]){
            return false;
        }
        return true;
    }
}
